package astar;

import java.util.ArrayList;
import java.util.List;

import data.GrapData;
import data.Point;
import data.PointList;

public class FindPath {
	private List<Point> closeList;
	private PointList openList;

	private Point start;
	private Point end;

	private int[][] grap;

	public FindPath(GrapData grapData) {
		closeList = new ArrayList<Point>();
		openList = new PointList();
		this.start = grapData.getStart();
		this.end = grapData.getEnd();
		this.grap = grapData.getGrap();
	}

	public List<Point> getPath() {
		openList.add(start);
		while (openList.size() != 0) {
			Point point = openList.first();
			if (point.equals(end)) {
				break;
			}
			
			// 将周围八个可达点加入开启列表
			addNeighborPointToOpen(point);

			// 将检查过的点加入到关闭列表
			closeList.add(point);
			openList.remove(point);
		}
		return getListPath(openList.first());
	}

	// 判断节点是否可以放入开启列表
	private boolean canAddToOpen(Point p) {
		// 检查点是否在地图内
		if (p.getY() < 0 || p.getY() >= grap.length || p.getX() < 0 || p.getX() >= grap[p.getY()].length) {
			return false;
		}

		// 检查点是否不可达
		if (grap[p.getY()][p.getX()] == GrapData.BAR) {
			return false;
		}

		// 检查是否存在close表中
		if (closeList.contains(p)) {
			return false;
		}
		return true;
	}

	private void addToOpen(Point checkPoint, Point p, int g) {
		// 检查点
		if (!canAddToOpen(checkPoint)) {
			return;
		}
		//检查斜向走的点
		if(GrapData.G_OBLIQUE == g && !checkOblique(p,checkPoint)){
			return;
		}
		// 计算当前点的G值
		checkPoint.setG(p.getG() + g);

		// 如果已加入该点
		if (openList.contains(checkPoint)) {
			// 若g值变小，则更新该点信息
			if (checkPoint.getG() < openList.get(checkPoint).getG()) {
				Point temp = openList.get(checkPoint);
				temp.setG(checkPoint.getG());
				temp.CalcF();
				temp.setParentPoint(p);
			}
		} else {
			checkPoint.setParentPoint(p);
			checkPoint.CalcH(end);
			checkPoint.CalcF();
			openList.add(checkPoint);
		}
	}

	//将相邻点加入到open列表
	private void addNeighborPointToOpen(Point point) {
		// 将周围八个可达点加入开启列表
		// x是列 y是行
		int x = point.getX();
		int y = point.getY();

		// 从左上角开始，顺时针计算
		// 左上
		addToOpen(new Point(x - 1, y - 1), point, GrapData.G_OBLIQUE);
		// 上
		addToOpen(new Point(x, y - 1), point, GrapData.G_DIRECT);
		// 右上
		addToOpen(new Point(x + 1, y - 1), point, GrapData.G_OBLIQUE);
		// 右
		addToOpen(new Point(x + 1, y), point, GrapData.G_DIRECT);
		// 右下
		addToOpen(new Point(x + 1, y + 1), point, GrapData.G_OBLIQUE);
		// 下
		addToOpen(new Point(x, y + 1), point, GrapData.G_DIRECT);
		// 左下
		addToOpen(new Point(x - 1, y + 1), point, GrapData.G_OBLIQUE);
		// 左
		addToOpen(new Point(x - 1, y), point, GrapData.G_DIRECT);
	}
	
	//通过回溯，生成路径。
	private List<Point> getListPath(Point p) {
		if (p == null) {
			return null;
		}

		List<Point> path = new ArrayList<>();
		while ((p = p.getParentPoint()) != null) {
			System.out.println(p.toString());
			path.add(p);
		}
		return path;
	}

	//只有斜向走的点，才会出现穿墙问题。
	//检查斜向走的点，之间的切点
	private boolean checkOblique(Point parent,Point p) {	
		//判断列方向变化的点      x = p.x
		int x =  p.getX();
		if(x >= 0 && x < grap[p.getY()].length){
			if(grap[parent.getY()][x] == GrapData.BAR){
				return false;
			}
		}

		//判断行方向变化的点     y = p.y
		int y = p.getY();
		if(y >= 0 && y < grap.length){
			if(grap[y][parent.getX()] == GrapData.BAR){
				return false;
			}
		}
		return true;
	}
	
	public static void main(String[] args) {
		// Point start = new Point(3, 1);
		// Point end = new Point(3, 5);
		// FindPath findPath = new FindPath(start, end);
		// Point point = findPath.getPath();
		// findPath.print(point);
	}
}
